'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-02 10:06:15
'''
'''
23. 合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6
'''

from typing import List
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:


        def merge2lists(l1, l2):
            if not l1:
                return l2
            if not l2:
                return l1
            head = None
            move = None
            if l1.val<=l2.val:
                head = l1
                l1 = l1.next
            else:
                head = l2
                l2 = l2.next
            move = head

            while l1 and l2:
                if l1.val<=l2.val:
                    move.next = l1
                    l1 = l1.next
                else:
                    move.next = l2
                    l2 = l2.next
                move = move.next
                # print(move.val)
            if l1:
                move.next = l1
            if l2:
                move.next = l2
            return head



        if len(lists) ==1:
            return lists[0]
        elif len(lists) == 0:
            return None
        else:
            media = int(len(lists)/2)
            l1 = self.mergeKLists(lists[:media])
            l2 = self.mergeKLists(lists[media:])
            return merge2lists(l1, l2)
if __name__ == "__main__":
    pass